import java.util.*;
public class Matrix
{
	private static int id[][] = new int[9][9];;
	private static boolean isPossible[][][];
	private static int allPossible[][];
	private static int possibleNum[][][];
	private static int x,y,num[][];//表示第x行，第y列的方格的第k个可能性正在检验。
	private static int firstx,firsty;
	private static int lastx,lasty;
	private static Random random;

	public static int[][]answer(int a[][]) 
	{
		int i,j,k,n;
		isPossible=new boolean[9][9][10];
		allPossible=new int[9][9];
		possibleNum=new int[9][9][10];
		num=new int[9][9];
		x=0; y=0;
		firstx=0;
		firsty=0;
		lastx=8;
		lasty=8;
		for(i=0;i<9;i++)
			for(j=0;j<9;j++)
			{
				for(k=0;k<10;k++)
				{
					isPossible[i][j][k]=false;
					possibleNum[i][j][k]=0;
				}	
				allPossible[i][j]=0;
				num[i][j]=0;
			}
		for(i=0;i<9;i++)
			for(j=0;j<9;j++)
			{
				id[i][j]=a[i][j];
				if(a[i][j]!=0)
				{
					isPossible[i][j][a[i][j]]=true;//标记已知
					allPossible[i][j]=1;//唯一的可能性
					possibleNum[i][j][0]=a[i][j];//第一个可能性是。。。
				}
			}
		for(i=0;i<9;i++)
			for(j=0;j<9;j++)
			if(a[i][j]==0)
			{
				n=0;
				for(k=1;k<10;k++)
				{
					if(allPossible[i][j]!=1)
						id[i][j]=k;//假设
					if(isFit(i,j)==true)//如果符合当前的环境
					{
						possibleNum[i][j][n]=k;
						n++;
						isPossible[i][j][k]=true;
					}
					if(allPossible[i][j]!=1)	id[i][j]=0;
				}
				allPossible[i][j]=n;
			}
		next:for(i=0;i<9;i++)
				for(j=0;j<9;j++)
				{
					if(allPossible[i][j]!=1)
					{
						firstx=i;
						firsty=j;
						break next;
					}
				}
		label:for(i=8;i>=0;i--)
				for(j=8;j>=0;j--)
				{
					if(allPossible[i][j]!=1)
					{
						lastx=i;
						lasty=j;
						break label;
					}
				}
		//以上部分属于对数据的整理，标记。
		while(true)
		{
			while(isTry())
			{
				if(allPossible[x][y]!=1) id[x][y]=possibleNum[x][y][num[x][y]];
				if(isFit(x,y))//如果合适
				{
					num[x][y]++;//为下一次该点的假设作准备
					if(x==lastx&&y==lasty)//最后一个且合适，则结束。
						return id;
					if(y<8) y++;
					else 
					{
					  x++;
					  y=0;
					}//下探
				}
				else  //不合适，则取消假设
				{
					num[x][y]++;
					if(allPossible[x][y]!=1)
						id[x][y]=0;
					//指定下一个。
				}
			}//直到找到不合适的为止。
			//以上部分属于下探。
			while(isBack())
			{
				num[x][y]=0;
				if(allPossible[x][y]!=1)	id[x][y]=0;
				if(y>0) y--;
				else 
				{
					x--;
					y=8;
				}
			}
			//以上部分属于回探
		}
	}
	private static boolean isFit(int a,int b)
	{
		if(allPossible[a][b]==1)
			return true;
		int i,j,l,m;
		for(i=0;i<9;i++)
		{
			if(i!=b&&id[a][i]==id[a][b])
				return false;
			if(i!=a&&id[i][b]==id[a][b])
				return false;
		}
		l=a/3;
		m=b/3;
		for(i=l*3;i<(l+1)*3;i++)
			for(j=m*3;j<(m+1)*3;j++)
				if((i!=a||j!=b)&&id[i][j]==id[a][b])
					return false;
		return true;
	}
	public static int get(int x,int y)
	{
		return id[x][y];
	}
	
	private static boolean isBack()
	{
		if(allPossible[x][y]==1) 
			return true; 
		return num[x][y]>=allPossible[x][y];
	}
	private static boolean isTry()
	{
		if(x==lastx&&y==lasty&&id[x][y]!=0)
			return false;
		if(allPossible[x][y]==1)
			return true;
		return num[x][y]<allPossible[x][y];
	}

	public static boolean check(int id[][],int a,int b)
	{
		int i,j,l,m;
		for(i=0;i<9;i++)
		{
			if(i!=b&&id[a][i]==id[a][b])
				return false;
			if(i!=a&&id[i][b]==id[a][b])
				return false;
		}
		l=a/3;
		m=b/3;
		for(i=l*3;i<(l+1)*3;i++)
			for(j=m*3;j<(m+1)*3;j++)
				if((i!=a||j!=b)&&id[i][j]==id[a][b])
					return false;
		return true;
	}
}

